package lc;
import org.junit.*;
public class Ex494 {
    class Solution {
        public int findTargetSumWays(int[] nums, int target) {
            int sum = 0, len = nums.length;
            for (int i = 0; i < len; i++) {
                sum += nums[i];
            }
            if (Math.abs(sum) < Math.abs(target)) {
                return 0;
            }
            //f[i][j]表示：以i-1为末尾元素，当前表达式值为sum+j的方案数
            int[][] f = new int[len + 1][2 * sum + 1];
            //初始化，i=0表示没有元素，只有f[0][target+sum]=1,其他未0
            f[0][sum] = 1;
            for (int i = 1; i <= len; i++) {
                for (int j = 0; j <= 2 * sum; j++) {
                    if (j >= nums[i - 1]) {
                        f[i][j] += f[i - 1][j - nums[i - 1]];
                    }
                    if (j + nums[i - 1] < 2 * sum + 1) {
                        f[i][j] += f[i - 1][j + nums[i - 1]];
                    }
                }
            }
            return f[len][sum + target];
        }
    }

    @Test
    public void test() {
        Solution s = new Solution();
        int[] nums = new int[]{1,1,1,1,1};
        System.out.println(s.findTargetSumWays(nums, 3));
    }

    @Test
    public void test1() {
        Solution s = new Solution();
        int[] nums = new int[]{1};
        System.out.println(s.findTargetSumWays(nums, 2));
        
    }
}
